package 二叉树;

import java.util.Arrays;

/**
 * TODO
 *
 * @Description
 * @Author Lx
 * @Date 2024/7/3 8:40
 **/
public class 由中后序构建二叉树 {

    public static void main(String[] args) {
        int[] inorder={9,3,15,20,7};
        int[] postorder={9,15,7,20,3};

        TreeNode root=buildTree(inorder,postorder);

        travelTree(root);
//        PrintBinaryTree.printTree(root);
//        PrintBinaryTree.treePrint(root);
    }

    //遍历二叉树
    static public void travelTree(TreeNode root){
        if(root==null){
            System.out.println("null");
            return;
        }

        System.out.println(root.val);
        travelTree(root.left);
        travelTree(root.right);
    }

    static public TreeNode buildTree(int[] inorder, int[] postorder) {
        //1.中序或后序为空
        if (inorder.length == 0||postorder.length==0) {
            return null;
        }


        //2.找root
        int rootval=postorder[postorder.length-1];


        //3.找切割点
        int endpoint=0;
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==rootval){
                endpoint=i;
                break;
            }
        }


        //4.开始切割
        //找左子树中后序
        int[] leftinorder = Arrays.copyOfRange(inorder, 0, endpoint);//左闭右开
        int[] leftpostorder = Arrays.copyOfRange(postorder, 0, endpoint);//左闭右开

        //找右子树中后序
        int[] rightinorder = Arrays.copyOfRange(inorder, endpoint+1, inorder.length);
        int[] rightpostorder = Arrays.copyOfRange(postorder, endpoint, inorder.length-1);

        //5.创建根节点
        TreeNode root=new TreeNode(rootval);

        //6.递归构建左右子树
        root.left=buildTree(leftinorder,leftpostorder);
        root.right=buildTree(rightinorder,rightpostorder);

        return root;
    }


}
